#include "main/utils.h"
using namespace std;

struct PrefixNode {
  PrefixNode* childern[26];
};

void insertWord(PrefixNode* root, const string& word) {
  auto node = root;
  for (auto ch : word) {
    if (node->childern[ch - 'a'] == nullptr) {
      node->childern[ch - 'a'] = new PrefixNode();
    }
    node = node->childern[ch - 'a'];
  }
}

PrefixNode* buildPrefixTree(const vector<string>& str_vec) {
  PrefixNode* root = new PrefixNode();
  for (auto word : str_vec) {
    reverse(word.begin(), word.end());
    insertWord(root, word);
  }
  return root;
}

void dfs(PrefixNode* node, int cur_length, int& sum_length) {
  bool is_leaf = true;
  for (int i = 0; i < 26; ++i) {
    if (node->childern[i]) {
      is_leaf = false;
      dfs(node->childern[i], cur_length + 1, sum_length);
    }
  }

  if (is_leaf) {
    sum_length += cur_length;
  }
}

int shorestEncoding(const vector<string>& str_vec) {
  PrefixNode* root = buildPrefixTree(str_vec);
  int cur_length = 1;
  int sum_length = 0;
  dfs(root, cur_length, sum_length);
  return sum_length;
}

int main() {
  vector<string> str_vec = {"time", "me", "bell"};
  cout << shorestEncoding(str_vec) << endl;

  vector<string> str_vec1 = {"tab", "tac"};
  cout << shorestEncoding(str_vec1) << endl;

  return 0;
}
